package 剑指offer_leetcode;

/**
 * JZ12矩阵中的路径
 */
public class 剑指Offer12_矩阵中的路径 {
    public boolean exist(char[][] board, String word) {
        if(board.length==0)
            return false;
        int n = board.length;
        int m = board[0].length;
        boolean[][] vis = new boolean[n][m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(helper(board,n,m,i,j,word,0,vis))
                    return true;
        return false;
    }

    boolean helper(char[][] board,int n, int m, int i, int j,String word, int k, boolean[][] vis){
        if(i<0 || i>=n || j<0 || j>=m || board[i][j]!=word.charAt(k) || vis[i][j]==true)
            return false;
        if(k==word.length()-1)
            return true;
        vis[i][j] = true;
        if(helper(board,n,m,i+1,j,word,k+1,vis) ||
                helper(board,n,m,i-1,j,word,k+1,vis) ||
                helper(board,n,m,i,j-1,word,k+1,vis) ||
                helper(board,n,m,i,j+1,word,k+1,vis) )
            return true;
        vis[i][j] = false;
        return false;
    }
}
